/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package cs;

import java.util.Scanner;

/**
 *
 * @author QuangHieu
 */

public class MySort {
    int a[];
    int b[];
    // tao mang ngau nhien
    void sinh(){
        int n;
        Scanner kb=new Scanner(System.in);
        System.out.print("Nhap so phan tu can sinh: ");
        n=kb.nextInt();
        a=new int [n+1];
        b=new int [n+1];
        for(int i=1;i<=n;i++){
            a[i]=(int)(Math.random()*1000);
            b[i]=a[i];
        }
    }

    //chep mang a sang mang b
    void chep(){
        System.arraycopy(b ,1, a,1, a.length-1);
    }

    // xuat mang
    void xuat(){
        for(int i=1;i<a.length;i++)
            System.out.print(" "+a[i]);
    }

    // sx chon
    void SelectSort(){
        for(int i=1;i<a.length;i++){
            int vtm=i; //gan vi tri min = i
            for(int j=i+1;j<a.length;j++){
                if(a[j]<a[vtm]) vtm=j;
            }
            if(i!=vtm){
                int t=a[i];
                a[i]=a[vtm];
                a[vtm]=t;
            }
        }
    }

    // sx chen
    void InsertSort(){
        for(int i=2;i<a.length;i++){
            int v=a[i];
            int k=i-1;
            while(k>0&& a[k]>v){
                a[k+1]=a[k];
                k--;
            }
            a[k+1]=v;
        }
    }

    //heapsort
     void heap(int start, int end){
        int j=start;
        while(2*j<=end){
            int maxChild=2*j;
            if(2*j<end && a[maxChild]<a[maxChild+1])
                maxChild=maxChild+1;
            if(a[j]<a[maxChild]){
                int t=a[j];
                a[j]=a[maxChild];
                a[maxChild]=t;
                j=maxChild;
            }
            else break;
        }
    }
     
    void heapSort(){
        int k=a.length-1;
        for(int i=k/2;i>0;i--) 
            heap(i,k);          //tao dong' ban dau
        for(int i=k;i>=1;i--){
            int t=a[i];         //hoan doi phan tu dau va phan tu cuoi
            a[i]=a[1];
            a[1]=t;
            heap(1,i-1);          //tao dong' lai
        }
    } 

    // MergeSort
    void merge(int low, int mid, int high)
   {
      int []b = new int[high-low+2];
      int h,i,j,k;
       h=low;
      i=0;
      j=mid+1;
      while((h<=mid)&&(j<=high))
      {
          if(a[h]<=a[j])  b[++i]=a[h++];
          else  b[++i]=a[j++];
      }
      if(h>mid)
        for(k=j;k<=high;k++)  b[++i]=a[k];
      else
        for(k=h;k<=mid;k++)   b[++i]=a[k];
      for(k=1;k<=high-low+1;k++)   a[k+low-1]=b[k];
   }

   void Merge_Sort(int low, int high)
   {
      if(low<high)
      {
        int mid=(low+high)/2;
        Merge_Sort(low,mid);
        Merge_Sort( mid+1,high);
        merge(low,mid,high);
      }
   }
   void Merge_Sort()
   {
      Merge_Sort(1, a.length-1);
   }

   //quick
   void qs(int l, int r)
    {
        int x= a[(l+r)/2];
        int i=l, j=r;
        while(i<j)
        {
            while(a[i]<x) i++;
            while(a[j]>x) j--;
            if(i<=j)
            {
                int t=a[i]; a[i]=a[j]; a[j]=t; i++; j--;
            }
        }
        if(i<r) qs(i,r);
        if(l<j) qs(l,j);
    }

    void Quick_Sort()
    {
        qs(1, a.length-1);
    }

    
    public static void main(String args[]){
        MySort ms=new MySort();
        ms.sinh();
        ms.xuat();
        double t1,t2;
        /*
        t1=System.currentTimeMillis();
        ms.SelectSort();
        t2=System.currentTimeMillis();
        System.out.println("Thoi gian"+(t2-t1));
        ms.chep();
        t1=System.currentTimeMillis();
        ms.InsertSort();
        t2=System.currentTimeMillis();
        System.out.println("Thoi gian"+(t2-t1));
        */ 
        t1=System.currentTimeMillis();
        ms.heapSort();
        t2=System.currentTimeMillis();
        System.out.println("Thoi gian"+(t2-t1));
        ms.xuat();
    }

}
